Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).

题目大意：给定2个已排序好的数组(大小分别为M和N)，找出2个数组中所有数的中位数，时间复杂度 O(log(M+N))

题目难度：Hard

/**
 * Created by gzdaijie on 16/5/3
 * 新建一个数组（M+N），遍历2个数组进行排序，再取新数组的中位数
 * 因为给定数组是有序的，复杂度为O(M+N)，居然能A
 * 当然有很多改进的地方，(1)遍历到总长度一半时停止，(2)不需要新建数组，2个临时变量，存下mid和mid-1
 * 但是仍改变不了复杂度是O(M+N)的事实
 */
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        // 其中一个为空，返回另一个数组的中位数
        if (len1 == 0) return this.getMedian(nums2);
        if (len2 == 0) return this.getMedian(nums1);
        // t1和t2指针分别指向nums1和nums2，较小的值赋值给nums，指针前移
        int t1 = 0;
        int t2 = 0;
        int index = 0;
        int[] nums = new int[len1 + len2];
        while (t1 < len1 && t2 < len2) {
            if(nums1[t1] <= nums2[t2]) {
                nums[index++] = nums1[t1++];
            } else {
                nums[index++] = nums2[t2++];
            }
        }
        // 剩下部分继续赋值
        if (t1 == len1) {
            while (t2 < len2) {
                nums[index++] = nums2[t2++];
            }
        } else {
            while (t1 < len1) {
                nums[index++] = nums1[t1++];
            }
        }
        return this.getMedian(nums);
    }

    public double getMedian(int[] nums) {
        int flag = (nums.length + 1) % 2;
        int mid = nums.length / 2;
        return (nums[mid] + nums[mid - flag]) / 2.0;
    }
}

/**
 * Created by gzdaijie on 16/5/3.
 * 假设求第k大的数, 切2个有序数组,(Left1, Right1) (Left2, Right2), Left1.length + Left2.length == k
 * 记Left1的最大值为L1, Right1的最大值为R1, 那么如果L1 < R2 && L2 < R1, 那么第k大的数字就是 max(L1, L2)
 * 首先,nums1的切口在c1（c1初始值为k）,nums2切口在k-c1, L1 > R2, c1需减小,L2 > R1, c1需增大
 * 切口位置可以使用二分法确定, 例如L1 > R2, c1需要减少,说明c1右边的切位都被排除,end = c1, 反之 start = c1
 * c1 = (start + end)/2
 * 复杂度 O(log(M+N))
 */
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        // 一方为空,返回另一数组的中值
        if (len1 == 0) return this.getMedian(nums2);
        if (len2 == 0) return this.getMedian(nums1);

        // 确保len1小于len2，减少二分次数
        if (len1 > len2) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // mid 中间位置, c1,c2记录切的位置, start,end用于二分确定切的位置
        int mid = len/2;
        int c1, c2;
        int start, end;
        int l1,l2,r1,r2;
        int MIN = Integer.MIN_VALUE;
        int MAX = Integer.MAX_VALUE;

        start = 0;
        end =  c1 = mid > len1 ? len1 : mid;
        c2 = mid - c1;

        while (true) {
            l1 = c1 == 0 ? MIN : nums1[c1 - 1];
            l2 = c2 == 0 ? MIN : nums2[c2 - 1];
            r1 = c1 == len1 ? MAX : nums1[c1];
            r2 = c2 == len2 ? MAX : nums2[c2];

            if (l1 <= r2 && l2 <= r1) {
                break;
            }
            if (l2 > r1) {
                start = c1;
            } else {
                end = c1;
            }
            c1 =  (start + end)/ 2;
            c2 = mid - c1;
        }

        if(len % 2 == 0) {
            return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;
        } else {
            return Math.min(r1, r2) * 1.0;
        }

    }

    public double getMedian(int[] nums) {
        int flag = (nums.length + 1) % 2;
        int mid = nums.length / 2;
        return (nums[mid] + nums[mid - flag]) / 2.0;
    }
}

参考：leetCode讨论区